﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.IO;

namespace TSP_Ant
{
    class Program
    {
        public static double alpha = 1.0;  //启发因子，信息素的重要程度
        public static double beta = 2.0;   //期望因子，城市间距离的重要程度
        public static double rou = 0.8;    //信息素残留参数


        public static int antCount = 2;  //蚂蚁数量
        public static int itCount = 40000;   //迭代次数
        public static int cityCount;            //城市数量

        public static double DBInit = 0.0;  //初始化信息素，设置成多少对结果影响不是太大，对算法收敛速度有些影响
        public static double DBQ = 100;   //总的信息素
        public static double DBMAX = 10e9; //一个标志数，10的9次方


        public static double[,] cityDistance;  //城市间的距离
        public static double[,] cityDB;        //城市间的信息素

        public static int[] xCityAry;    //城市x坐标
        public static int[] yCityAry;    //城市y坐标

        public static double[,] dbTempArray;

        public static Random rand = new Random();

        static void Main(string[] args)
        {
            readData(@"D:\tsplib\rand50.tsp");
            //readData(@"D:\test4.tsp");

            Tsp tsp = new Tsp();
            tsp.init();
            tsp.search();

            Console.WriteLine(tsp.bestAnt.antPathLength);


        }


        public static void readData(String filename)
        {
            StreamReader sr = new StreamReader(filename);
            String str;
            sr.ReadLine();
            sr.ReadLine();
            sr.ReadLine();
            str = sr.ReadLine();
            cityCount = Int32.Parse(str.Trim().Split(' ')[2]);

            cityDistance = new double[cityCount, cityCount];
            cityDB = new double[cityCount, cityCount];

            sr.ReadLine();
            sr.ReadLine();

            xCityAry = new int[cityCount];
            yCityAry = new int[cityCount];

            for (int i = 0; i < cityCount; i++ )
            {
                str = sr.ReadLine();
                String[] sstr = str.Trim().Split(' ');
                xCityAry[i] = Int32.Parse(sstr[1]);
                yCityAry[i] = Int32.Parse(sstr[2]);
            }

            sr.Close();

        }

        public class Ant
        {
            public int[] antPath;  //蚂蚁走过的路径
            public double antPathLength; //蚂蚁走过的路径长度

            int antCurrentCity;  //当前所在城市编号
            int antMovedCityCount; //去过的城市数量
            Boolean[] antCityMoved; //标记是否已经去过某城市

            public void init()
            {
                this.antPath = new int[cityCount];
                this.antCityMoved = new Boolean[cityCount];
                
                for (int i = 0; i < cityCount; i++)
                {
                    antCityMoved[i] = false;  //设置所有city都没有去过
                    antPath[i] = -1;           //所有路径清空
                }

                //随机选取一个城市作为起点
                antPathLength = 0.0;
                antCurrentCity = rand.Next(0, cityCount);
                antPath[0] = antCurrentCity;
                antCityMoved[antCurrentCity] = true;
                antMovedCityCount = 1;

            }

            public int nextCity()
            {
                int selectedCity = -1;

                //计算当前城市和没去过的城市之间的信息素之和
                double totalDB = 0;
                double[] prob = new double[cityCount];

                //计算所有候选点的概率
                for (int i = 0; i < cityCount; i++ )
                {
                    if (!antCityMoved[i] && antCurrentCity != i)
                    {
                        prob[i] = Math.Pow(cityDB[antCurrentCity, i], alpha) * Math.Pow(1.0 / cityDistance[antCurrentCity, i], beta);
                        totalDB += prob[i];
                    }
                    else
                        prob[i] = 0;
                }

                //轮盘选择
                double tempDB = 0.0;
                if (totalDB > 0.0)
                {
                    tempDB = rand.NextDouble() * totalDB;

                    for (int i = 0; i < cityCount; i++ )
                    {
                        if (!antCityMoved[i])
                        {
                            tempDB = tempDB - prob[i];
                            if (tempDB < 0.0)
                            {
                                selectedCity = i;
                                return selectedCity;
                            }
                        }
                    }
                }

                //如果城市间的信息素非常小 ( 小到比double能够表示的最小的数字还要小 )
                //那么由于浮点运算的误差原因，上面计算的概率总和可能为0
                //会出现经过上述操作，没有城市被选择出来
                //出现这种情况，就把第一个没去过的城市作为返回结果   
                if (selectedCity == -1)
                {
                    for (int i = 0; i < cityCount; i++ )
                    {
                        if (!antCityMoved[i] && antCurrentCity != i)
                        {
                            selectedCity = i;
                            return selectedCity;
                        }
                    }
                }

                return selectedCity;
            }

            public void antMove()
            {
                int nextCityID = nextCity();

                antPath[antMovedCityCount] = nextCityID;
                antCityMoved[nextCityID] = true;
                antCurrentCity = nextCityID;
                antMovedCityCount++;
            }

            public void antSearch()
            {
                init();
                
                while (antMovedCityCount < cityCount)
                {
                    antMove();
                }

                calcPathLength();

            }

            public void calcPathLength()
            {
                antPathLength = 0;

                for (int i = 1; i < cityCount; i++ )
                {
                    antPathLength += cityDistance[antPath[i], antPath[i - 1]];
                }

                antPathLength += cityDistance[antPath[cityCount-1], antPath[0]];
            }


        }//end of class Ant

        public class Tsp
        {
            public Ant[] antArray;
            public Ant bestAnt;

            public void init()
            {
                antArray = new Ant[antCount];
                
                bestAnt = new Ant();
                for (int i = 0; i < antCount; i++)
                    antArray[i] = new Ant();

                bestAnt.antPathLength = DBMAX;
                double tempDB = 0;

                //计算两城市间距离
                for (int i = 0; i < cityCount; i++ )
                {
                    for (int j = 0; j < cityCount; j++)
                    {
                        tempDB = (xCityAry[i] - xCityAry[j]) * (xCityAry[i] - xCityAry[j]) + (yCityAry[i] - yCityAry[j]) * (yCityAry[i] - yCityAry[j]);
                        tempDB = Math.Round(tempDB);
                        cityDistance[i, j] = Math.Sqrt(tempDB);
                    }
                }

                //初始化城市间的信息素,设置成多少对结果影响不是太大，对算法收敛速度有些影响
                for (int i = 0; i < cityCount; i++)
                {
                    for (int j = 0; j < cityCount; j++)
                    {
                        cityDB[i, j] = DBInit;
                    }
                }

            }

            public void updateTrial()
            {
                double[,] dbTempArray = new double[cityCount, cityCount];
                for (int i = 0; i < cityCount; i++)
                {
                    for (int j = 0; j < cityCount; j++)
                    {
                        dbTempArray[i, j] = 0;
                    }
                }

                //计算每只蚂蚁留下的信息素
                int m = 0, n = 0;
                for (int i = 0; i < antCount; i++)
                {
                    for (int j = 1; j < cityCount; j++)
                    {
                        m = antArray[i].antPath[j];
                        n = antArray[i].antPath[j - 1];
                        dbTempArray[n, m] += DBQ / antArray[i].antPathLength;
                        dbTempArray[m, n] = dbTempArray[n, m];                  }

                    //路径首尾城市间的信息素
                    n = antArray[i].antPath[0];
                    dbTempArray[n, m] += DBQ / antArray[i].antPathLength;
                    dbTempArray[m, n] = dbTempArray[n, m];
                }

                for (int i = 0; i < cityCount; i++)
                {
                    for (int j = 0; j < cityCount; j++)
                    {
                        //最新的环境信息素=残留信息素+新留下的信息素
                        cityDB[i, j] = cityDB[i, j] * rou + dbTempArray[i, j];
                    }
                }
            }

            public void search()
            {
                //迭代循环
                for (int i = 0; i < itCount; i++ )
                {
                    //蚂蚁搜索循环
                    for (int j = 0; j < antCount; j++ )
                    {
                        antArray[j].antSearch();

                        if (antArray[j].antPathLength < bestAnt.antPathLength)
                        {
                            bestAnt = antArray[j];
                        }
                    }

                    Console.WriteLine(bestAnt.antPathLength);

                    //更新环境信息素
                    updateTrial();
                }
            }

        }//end of class Tsp

    }



    
}